package lc_剑指_Offer_II_106_二分图;

import java.util.ArrayList;
import java.util.List;

public class Solution {

	Boolean[] br;
	List<List<Integer>> nexts;

	public boolean isBipartite(int[][] graph) {
		nexts = new ArrayList<>();
		for (int i = 0; i < graph.length; i++) {
			List<Integer> list = new ArrayList<>();
			for (int v : graph[i]) {
				list.add(v);
			}
			nexts.add(list);
		}
		br = new Boolean[graph.length];
		for (int i = 0; i < graph.length; i++) {
			if (br[i] == null && !f(i, true)) {
				return false;
			}
		}
		return true;
	}

	private boolean f(int index, boolean flag) {
		if (br[index] != null) {
			if (br[index] == flag) {
				return true;
			}
			return false;
		}
		br[index] = flag;
		for (int n : nexts.get(index)) {
			if (!f(n, !flag)) {
				return false;
			}
		}
		return true;
	}

}